package com.heima.datastructure.binarytree;

import com.heima.datastructure.binarysearchtree.BSTNode;

import java.util.LinkedList;
import java.util.function.Consumer;

/**
 * <strong>   树的深度优先遍历</strong>
 * <strong>和 树的广度优先遍历</strong>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/7 18:55
 */
public class TreeTraversal {

    // 递归深度优先遍历

    /**
     * <strong>前序遍历</strong>
     * <ol>
     *     <li>获取当前树根节点的值</li>
     *     <li>前序遍历左子树</li>
     *     <li>前序遍历右子树</li>
     * </ol>
     * @param root 当前树的根节点
     * @param consumer 消费者，接收遍历到的节点值
     */
    public static <E> void preOrder(TreeNode<E> root, Consumer<E> consumer){
        // 递归退出条件：当前树为空
        if (root == null){
            return;
        }
        // 获取当前节点值，交给消费者接受
        consumer.accept(root.value);
        // 遍历左子树
        preOrder(root.left, consumer);
        // 遍历右子树
        preOrder(root.right,consumer);
    }

    /**
     * <strong>二叉搜索树的前序遍历</strong>
     * @param root 树的根节点
     * @param consumer 消费者，接收遍历到的节点
     * @param <K> 二叉搜索树节点的key属性的类型，必须实现Comparable接口
     * @param <V> 二叉搜索树节点的value属性，用来存放数据
     */
    public static <K extends Comparable<K>,V> void preOrder(BSTNode<K,V> root, Consumer<BSTNode<K,V>> consumer){
        if (root == null){
            return;
        }
        consumer.accept(root);
        preOrder(root.left,consumer);
        preOrder(root.right,consumer);
    }

    /**
     * <strong>中序遍历</strong>
     * <ol>
     *     <li>中序遍历左子树</li>
     *     <li>获取当前树根节点的值</li>
     *     <li>中序遍历右子树</li>
     * </ol>
     * @param root 当前树的根节点
     * @param consumer 消费者，接收遍历到的节点
     */
    public static <E> void inOrder(TreeNode<E> root, Consumer<E> consumer){
        // 递归终止条件：当前树为空
        if (root == null){
            return;
        }
        // 中序遍历左子树
        inOrder(root.left,consumer);
        // 获取当前树根节点的值
        consumer.accept(root.value);
        // 中序遍历右子树
        inOrder(root.right,consumer);
    }

    /**
     * <strong>二叉搜索树的中序遍历</strong>
     * <h3>二叉搜索树的中序遍历结果就是所有节点按key升序的结果</h3>
     * @param root 树的根节点
     * @param consumer 消费者，接收遍历到的节点
     * @param <K> 二叉搜索树节点的key属性的类型，必须实现Comparable接口
     * @param <V> 二叉搜索树节点的value属性，用来存放数据
     */
    public static <K extends Comparable<K>,V> void inOrder(BSTNode<K,V> root, Consumer<BSTNode<K,V>> consumer){
        if (root == null){
            return;
        }
        inOrder(root.left,consumer);
        consumer.accept(root);
        inOrder(root.right,consumer);
    }

    /**
     * <strong>后序遍历</strong>
     * <ol>
     *     <li>后序遍历左子树</li>
     *     <li>后序遍历右子树</li>
     *     <li>获取当前树根节点的值</li>
     * </ol>
     * @param root 当前树的根节点
     * @param consumer 消费者，接收遍历到的节点值
     */
    public static <E> void postOrder(TreeNode<E> root, Consumer<E> consumer){
        // 递归终止条件：当前树为空
        if (root == null){
            return;
        }
        // 后序遍历左子树
        postOrder(root.left,consumer);
        // 后序遍历右子树
        postOrder(root.right,consumer);
        // 获取当前树根节点的值
        consumer.accept(root.value);
    }

    /**
     * <strong>二叉搜索树的后序遍历</strong>
     * @param root 树的根节点
     * @param consumer 消费者，接收遍历到的节点
     * @param <K> 二叉搜索树节点的key属性的类型，必须实现Comparable接口
     * @param <V> 二叉搜索树节点的value属性，用来存放数据
     */
    public static <K extends Comparable<K>,V> void postOrder(BSTNode<K,V> root, Consumer<BSTNode<K,V>> consumer){
        if (root == null){
            return;
        }
        postOrder(root.left,consumer);
        postOrder(root.right,consumer);
        consumer.accept(root);
    }

    // 广度优先遍历

    /**
     * <strong>树的层序遍历</strong>
     * <ol>
     *     <li>建立一个存放树节点的队列，把根节点插入队列中</li>
     *     <li>当前层节点数置为1，下一层节点数置为0</li>
     *     <li>从第一层开始遍历，依次取出队列中当前层的节点，如果有子节点，则依次加到队列中</li>
     *     <li>并且下一层的节点数也要自增，消费者取走遍历到的节点值</li>
     * </ol>
     * @param root 当前树的根节点
     * @param consumer 消费者，接收遍历到的节点的值
     */
    public static <E> void levelOrder(TreeNode<E> root, Consumer<E> consumer){ // 层数从1编号
        LinkedList<TreeNode<E>> queue = new LinkedList<>();
        if (root == null){
            return;
        }
        queue.offer(root);
        int curLevel = 1; // 当前层节点个数
        int nextLevel = 0; // 下一层节点个数
        while (!queue.isEmpty()){
            // 一次for循环就是处理一层
            for (int i = 0; i < curLevel; i++) {
                TreeNode<E> node = queue.poll();
                // 有左子节点，则加入到队列中，下一层节点数加一
                assert node != null; // 没必要
                if (node.left != null){
                    queue.offer(node.left);
                    nextLevel++;
                }
                // 有右子节点，则加入到队列中，下一层节点数加一
                if (node.right != null){
                    queue.offer(node.right);
                    nextLevel++;
                }
                // 接收节点的值
                consumer.accept(node.value);
            }
            curLevel = nextLevel;
            nextLevel = 0;
        }
    }

    /**
     * <strong>二叉搜索树的层序遍历</strong>
     * @param root 二叉搜索树的头节点
     * @param consumer 消费者，消费遍历到的节点
     * @param <K> 二叉搜索树节点key的类型，要实现Comparable接口
     * @param <V> 二叉搜索树节点value的类型
     */
    public static <K extends Comparable<K>, V> void levelOrder(BSTNode<K, V> root, Consumer<BSTNode<K, V>> consumer){
        LinkedList<BSTNode<K, V>> queue = new LinkedList<>();
        if (root == null){
            return;
        }
        queue.offer(root);
        while (!queue.isEmpty()){
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++){
                BSTNode<K, V> node = queue.poll();
                assert node != null;
                if (node.left != null){
                    queue.add(node.left);
                }
                if (node.right != null){
                    queue.add(node.right);
                }
                consumer.accept(node);
            }
        }
    }

    // 非递归深度优先遍历

    /**
     * <strong>沿二叉树边缘走一圈，从左往右</strong><br><br>
     * <h3>非递归的对二叉树进行遍历，能处理前序遍历和中序遍历</h3>
     * <h3>递归深度优先遍历的三种遍历方式：前序、中序、后序：虽然结果不同，但是遍历时走的路是一模一样的，都是沿着二叉树的边缘走一圈</h3>
     * <ol>
     *     <li>从根节点出发往左子节点方向一直走到底，可以保证第一部分的沿着边缘遍历</li>
     *     <li>因为还要往回走，所以需要一个数据结构用来记录来时路，栈就很合适</li>
     *     <li>走到底后，指针返回到上一个节点，再判断，是否存在右子节点，因为要保证沿着边缘遍历</li>
     *     <li>如果有右子节点，则指针应当改到右子节点继续遍历，也就是往左走到底，再返回此时栈里上一个节点，看有没有右子节点</li>
     *     <li>也就是处理左子节点，然后需要处理右子节点为根节点的右子树</li>
     *     <li>如果没有右子节点，看上上个节点的右分岔是否可走</li>
     *     <li>……</li>
     * </ol>
     * @param root 当前树的根节点
     * @param consumer1 消费者，接收前序遍历到的节点
     * @param consumer2 消费者，接收中序遍历到的节点
     */
    public static <E> void order1(TreeNode<E> root, Consumer<E> consumer1, Consumer<E> consumer2){
        TreeNode<E> curr = root;
        LinkedList<TreeNode<E>> stack = new LinkedList<>(); // 存放树节点的栈
        while (curr != null || !stack.isEmpty()){ // curr != null是在一直找左子树，直到左子树为null，接下来就该处理同级的右子树了，当右子树处理完了，就该处理上一级的右子树了
            if (curr != null) { // 如果curr不为空那就已知往左深入
                consumer1.accept(curr.value); // 去，前序遍历的遍历结果，因为前序遍历是根左右的顺序，curr不断左下的过程就是不断的缩小左子树，而每次获取curr在缩小之前，当左到底后才会处理右边，所以是根左右
                stack.push(curr); // 记录来时路
                curr = curr.left; // 往左深入         左子树
            }else { // curr为空，说路到头了，要回头走上一个节点的右分岔
                TreeNode<E> last = stack.pop(); // 获取上一个节点            值
                consumer2.accept(last.value); // 回，中序遍历的遍历结果，因为中序遍历是左根右的顺序，当往左到底的时候，说明最左最小的左子树遍历完成，返回上一级，获取curr之后再指向右子树
                curr = last.right; // 上个节点有右分岔可走，则让curr指向右分岔的节点，非空，则会继续往左深入。如果上个节点没有右分岔，那么也可让curr指向null          右子树
            }
        }
    }

    /**
     * <h3>非递归的对二叉树进行遍历，能够实现前序遍历和后序遍历</h3>
     * @param root 根节点
     * @param consumer1 消费者1，接收前序遍历的结果
     * @param consumer2 消费者2，接收后序遍历的结果
     * @param <E> 树节点值的类型
     */
    public static <E> void order2(TreeNode<E> root, Consumer<E> consumer1, Consumer<E> consumer2){
        LinkedList<TreeNode<E>> stack = new LinkedList<>();
        TreeNode<E> curr = root;
        TreeNode<E> lastPop = null;
        while (curr != null || !stack.isEmpty()){
            if (curr != null) {
                consumer1.accept(curr.value); // 前序遍历的结果
                stack.push(curr);
                curr = curr.left; //    左子树
            }else {
                TreeNode<E> last = stack.peek(); // 回头处理last为根节点的树，很明显，这棵树的左子树已经处理完毕。当这棵树处理完了再弹出这棵树的根节点
                if (last.right == null || last.right == lastPop){ // 没有右子树，或者栈顶节点的右子树的根节点等于上次弹出栈顶的节点，那么last为根节点的树处理完毕。         右子树
                    consumer2.accept(last.value); // 后序遍历的结果，因为代码的思想就是先处理最小的左子树，然后处理同级的右子树，最后再获取上一级的的节点值，也就是左子树和右子树的根节点的父节点  值
                    lastPop = stack.pop(); // 用于记录上次弹出栈顶的节点
                }else {
                    curr = last.right; // 处理右子树，但是会陷入死循环，当处理完右子树时，栈顶就是last节点，curr也是null，又last节点有右子树，就会一直不间断的处理右子树
                }
            }
        }
    }

    /**
     * <h3>非递归的对二叉树进行遍历，能够实现前序、中序、后序</h3>
     * <ol>
     *     <li>采用的遍历方式是左子树->右子树->根节点的顺序，也就是仿造后序遍历的顺序</li>
     *     <li>将代码逻辑分为左子树处理前，右子树处理前，右子树处理后几个逻辑，好在合适的地方接收遍历结果</li>
     * </ol>
     * @param root 树的根节点
     * @param consumer1 消费者1，接收前序遍历的结果
     * @param consumer2 消费者2，接收中序遍历的结果
     * @param consumer3 消费者3，接收后序遍历的结果
     * @param <E> 二叉树节点的值类型
     */
    public static <E> void order(TreeNode<E> root, Consumer<E> consumer1, Consumer<E> consumer2, Consumer<E> consumer3){
        LinkedList<TreeNode<E>> stack = new LinkedList<>();
        TreeNode<E> curr = root;
        TreeNode<E> lastPop = null; // 用于存放上一次弹出栈顶的节点。因为我们采用后序的方式遍历，所以树的头节点时最后访问的，所以当上一次弹出的节点是当前遍历的树的头节点的右子节点时，说明右子树已经遍历完成，接下来应该轮到当前树的头节点
        while (curr != null || !stack.isEmpty()){
            // 待处理左子树
            if (curr != null) {
                stack.push(curr); // 压栈，记录来时路
                consumer1.accept(curr.value); // 前序遍历
                curr = curr.left; // 处理左子树
            }else {
                TreeNode<E> last = stack.peek();
                // 右子树为空
                if (last.right == null){ // 右子树为空，处理完毕，轮到当前树的头节点
                    consumer2.accept(last.value); // 中序遍历
                    lastPop = stack.pop(); // 进行pop弹栈操作时，说明在往回走，如果curr的父节点是last（curr的父节点可能不是last的，回的时候高度比较高时），last的右子节点为空，curr也为null，说明last是叶子节点。也就是说这里的pop操作弹出的是一个叶子节点，所以没被弹出之前栈的大小size就是根节点到这个叶子节点last的深度（从1计数）
                    consumer3.accept(lastPop.value); // 后序遍历
                }
                // 右子树处理完毕
                else if (last.right == lastPop) { // 右子树处理完毕，轮到当前树的头节点
                    lastPop = stack.pop();
                    consumer3.accept(lastPop.value); // 后序遍历
                }
                // 待处理右子树
                else {
                    consumer2.accept(last.value); // 中序遍历
                    curr = last.right; // 处理右子树
                }
            }
        }
    }
}
